package pnu.ssm.sort;

public class InsertionSort {
	// Order of N^2 
	// Quicker than Bubble, Selection Sort
	public static void main(String[] args) {
		int arr[] = { 100,22,44,52,1834,183,11,0,-11,-52 };
		
		for (int i=1; i<arr.length; i++){ 
			// i-1 까지는 모두 정렬이 되어 있다.
			int temp = arr[i];   // i 번째 값이 이미 정렬되어 있는 [0, i-1] 중에 어디에 위치 해야 할지를 정해야 한다.
			int pos = i-1; // pos는 정렬되어 있는 값만을 가리킨다.
			while(true){
				if( pos < 0 || arr[pos] < temp)
					break;
				arr[pos+1] = arr[pos]; // 교환이 아니라, 뒤로 복사한다.
				pos--;
			}
			arr[pos+1] = temp; // temp의 위치를 찾았으니 넣어준다.
		}
		
		for(int i=0; i<arr.length; i++){
			System.out.print(arr[i] + " ");
		}
	}
}
